METRIC 2011 Trimester at Institut Henri Poincaré (Paris, France)<br />Workshop on Expanders and derandomization (March 21-25, 2011)<br />Mar 23, 16:30-17:30 - Avi Wigderson (IAS Princeton)<br />Popular's talk at the École Normale Supérieure de Paris<br />The P vs. NP problem: Internet security, efficient computations and the limits of human knowledge<br />----<br />The P versus NP problem is a precise, easy to state mathematical problem.<br />Yet it stands unique in the philosophical meaning, and the impacts of its resolution.<br /><br />If P equals NP, then we can hope to quickly answer most other mathematical and scientific challenges we face. If P does not equal NP, we can hope to make the security of electronic interactions unconditional.<br /><br />In the talk I'll formulate the P versus NP problem, and explain these far reaching connections. I'll describe the research it has spun in Computational Complexity, and report on the attempts to resolve it.
